package com.lzq.leetcode.hoot100;

import com.lzq.leetcode.hoot100.ds.ListNode;

import java.util.List;

public class s148 {

    public static void main(String[] args) {
        s148 s148 = new s148();
        System.out.println(s148.sortList(new ListNode(new int[]{4, 2, 1, 3})));
    }

    public ListNode sortList(ListNode head) {

        // 统计长度
        ListNode tempHead = new ListNode();
        tempHead.next = head;

        int len = 0;
        ListNode p = head;
        while (p != null) {
            p = p.next;
            ++len;
        }
        // 分组
        int pLen = 1;
        while (pLen < len) {

            ListNode pre = tempHead;
            ListNode next = tempHead.next;
            pre.next = null;
            while (next != null) {
                // 找到两个分组
                ListNode h1 = next;
                next = getSub(next, pLen);
                ListNode h2 = next;
                next = getSub(next, pLen);
                // 合并
                while (h1 != null || h2 != null) {
                    int val1 = h1 == null ? Integer.MAX_VALUE : h1.val;
                    int val2 = h2 == null ? Integer.MAX_VALUE : h2.val;
                    if (val1 < val2) {
                        pre.next = h1;
                        h1 = h1.next;
                    } else {
                        pre.next = h2;
                        h2 = h2.next;
                    }
                    pre = pre.next;
                }
            }
            pLen *= 2;
        }

        return tempHead.next;
    }

    // 返回尾部的下一个元素
    private ListNode getSub(ListNode head, int len) {
        if (head == null)   return null;
        while (head.next != null && len > 1) {
            --len;
            head = head.next;
        }
        ListNode next = head.next;
        head.next = null;
        return next;
    }
}
